// 题解链接:https://leetcode.cn/problems/sfvd7V/solutions/2250199/yi-ti-duo-jie-by-leyi_999-nyd4/
// 方法一
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution
{
public:
    // cited from:
    // https://stackoverflow.com/questions/20511347/a-good-hash-function-for-a-vector
    // equivalent to : hash_combine() (from boost lib)
    struct HashFunc_t
    {
        size_t operator()(const vector<int> &key) const
        {
            std::hash<int> hasher;
            size_t seed = 0;
            for (int i : key)
            {
                seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
            }
            return seed;
        }
    };
    vector<vector<string>> groupAnagrams(vector<string> &strs)
    {
        vector<vector<string>> ret;
        unordered_map<vector<int>, vector<string>, HashFunc_t> u_map;
        for (auto &e : strs)
        {
            vector<int> count_vt(26);
            for (auto &c : e)
            {
                count_vt[c - 'a']++;
            }
            u_map[count_vt].push_back(e);
        }
        for (auto e : u_map)
        {
            ret.push_back(std::move(e.second));
        }
        return ret;
    }
};
// 方法二
#include <algorithm>
using namespace std;
class Solution
{
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs)
    {
        vector<vector<string>> ret;
        unordered_map<string, vector<string>> u_map;
        for (auto &e : strs)
        {
            string key(e);
            sort(key.begin(), key.end());
            u_map[std::move(key)].push_back(std::move(e));
        }
        for (auto e : u_map)
        {
            ret.push_back(std::move(e.second));
        }
        return ret;
    }
};
